package exam.shenxinfu.S1;

public class Solution {

    public static final int[] dx = {0, 0, -1, 1};
    public static final int[] dy = {-1, 1, 0, 0};
    public int m = 0;
    public int n = 0;
    public int res = 0;

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param grid int整型二维数组
     * @return int整型
     */
    public int ncov_defect (int[][] grid) {
        m = grid.length;
        if (m == 0)
            return 0;
        n = grid[0].length;
        if (n == 0)
            return 0;

        boolean[][] visited = new boolean[m][n];
        int result = 0;
        for (int i=0; i<m; ++i) {
            for (int j=0; j<n; ++j) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    res = 0;
                    dfs(grid, i, j, visited);
                    result += res;
                }
            }
        }
        return result;
    }

    private void dfs(int[][] grid, int x, int y, boolean[][] visited) {
        visited[x][y] = true;
        for (int i=0; i<4; ++i) {
            int newx = x + dx[i], newy = y + dy[i];
            if (!valid(newx, newy))
                continue;
            if (grid[newx][newy] == 1) {
                if (!visited[newx][newy])
                    dfs(grid, newx, newy, visited);
            } else if (grid[newx][newy] == 0) {
                res++;
                grid[newx][newy] = 2;
            }
        }
    }

    private boolean valid(int x, int y) {
        if (x < 0 || x >= m || y < 0 || y >= n)
            return false;
        return true;
    }
}